/*
 * Copyright The Apache Software Foundation.
 * This class is based on org.apache.IntHashMap.commons.lang
 * http://jakarta.apache.org/commons/lang/xref/org/apache/commons/lang/IntHashMap.html
 * It was adapted by Bruno Lowagie for use in iText,
 * reusing methods that were written by Paulo Soares.
 * Instead of being a hashtable that stores objects with an int as key,
 * it stores int values with an int as key.
 *
 * This is the original license of the original class IntHashMap:
 *
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 * Note: originally released under the GNU LGPL v2.1,
 * but rereleased by the original author under the ASF license (above).
 */
package com.itextpdf.text.pdf;

// import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;

import com.itextpdf.text.error_messages.MessageLocalization;

/***
 * <p>A hash map that uses primitive ints for the key rather than objects.</p>
 *
 * <p>Note that this class is for internal optimization purposes only, and may
 * not be supported in future releases of Jakarta Commons Lang.  Utilities of
 * this sort may be included in future releases of Jakarta Commons Collections.</p>
 *
 * @author Justin Couch
 * @author Alex Chaffee (alex@apache.org)
 * @author Stephen Colebourne
 * @author Bruno Lowagie (change Objects as keys into int values)
 * @author Paulo Soares (added extra methods)
 */
public class IntHashtable implements Cloneable {

    /***
     * The hash table data.
     */
    private transient Entry table[];

    /***
     * The total number of entries in the hash table.
     */
    private transient int count;

    /***
     * The table is rehashed when its size exceeds this threshold.  (The
     * value of this field is (int)(capacity * loadFactor).)
     *
     * @serial
     */
    private int threshold;

    /***
     * The load factor for the hashtable.
     *
     * @serial
     */
    private float loadFactor;

    /***
     * <p>Constructs a new, empty hashtable with a default capacity and load
     * factor, which is <code>20</code> and <code>0.75</code> respectively.</p>
     */
    public IntHashtable() {
        this(150, 0.75f);
    }
//
//    /***
//     * <p>Constructs a new, empty hashtable with the specified initial capacity
//     * and default load factor, which is <code>0.75</code>.</p>
//     *
//     * @param  initialCapacity the initial capacity of the hashtable.
//     * @throws IllegalArgumentException if the initial capacity is less
//     *   than zero.
//     */
//    public IntHashtable(int initialCapacity) {
//        this(initialCapacity, 0.75f);
//    }
//
//    /***
//     * <p>Constructs a new, empty hashtable with the specified initial
//     * capacity and the specified load factor.</p>
//     *
//     * @param initialCapacity the initial capacity of the hashtable.
//     * @param loadFactor the load factor of the hashtable.
//     * @throws IllegalArgumentException  if the initial capacity is less
//     *             than zero, or if the load factor is nonpositive.
//     */
    public IntHashtable(int initialCapacity, float loadFactor) {
        super();
        if (initialCapacity < 0) {
            throw new IllegalArgumentException(MessageLocalization.getComposedMessage("illegal.capacity.1", initialCapacity));
        }
        if (loadFactor <= 0) {
            throw new IllegalArgumentException(MessageLocalization.getComposedMessage("illegal.load.1", String.valueOf(loadFactor)));
        }
        if (initialCapacity == 0) {
            initialCapacity = 1;
        }
        this.loadFactor = loadFactor;
        table = new Entry[initialCapacity];
        threshold = (int) (initialCapacity * loadFactor);
    }
//
//    /***
//     * <p>Returns the number of keys in this hashtable.</p>
//     *
//     * @return  the number of keys in this hashtable.
//     */
//    public int size() {
//        return count;
//    }
//
//    /***
//     * <p>Tests if this hashtable maps no keys to values.</p>
//     *
//     * @return  <code>true</code> if this hashtable maps no keys to values;
//     *          <code>false</code> otherwise.
//     */
//    public boolean isEmpty() {
//        return count == 0;
//    }
//
//    /***
//     * <p>Tests if some key maps into the specified value in this hashtable.
//     * This operation is more expensive than the <code>containsKey</code>
//     * method.</p>
//     *
//     * <p>Note that this method is identical in functionality to containsValue,
//     * (which is part of the Map interface in the collections framework).</p>
//     *
//     * @param      value   a value to search for.
//     * @return     <code>true</code> if and only if some key maps to the
//     *             <code>value</code> argument in this hashtable as
//     *             determined by the <tt>equals</tt> method;
//     *             <code>false</code> otherwise.
//     * @throws  NullPointerException  if the value is <code>null</code>.
//     * @see        #containsKey(int)
//     * @see        #containsValue(int)
//     * @see        java.util.Map
//     */
//    public boolean contains(int value) {
//
//        Entry tab[] = table;
//        for (int i = tab.length; i-- > 0;) {
//            for (Entry e = tab[i]; e != null; e = e.next) {
//                if (e.value == value) {
//                    return true;
//                }
//            }
//        }
//        return false;
//     }
//
//    /***
//     * <p>Returns <code>true</code> if this HashMap maps one or more keys
//     * to this value.</p>
//     *
//     * <p>Note that this method is identical in functionality to contains
//     * (which predates the Map interface).</p>
//     *
//     * @param value value whose presence in this HashMap is to be tested.
//     * @return boolean <code>true</code> if the value is contained
//     * @see    java.util.Map
//     * @since JDK1.2
//     */
//    public boolean containsValue(int value) {
//        return contains(value);
//    }
//
//    /***
//     * <p>Tests if the specified int is a key in this hashtable.</p>
//     *
//     * @param  key  possible key.
//     * @return <code>true</code> if and only if the specified int is a
//     *    key in this hashtable, as determined by the <tt>equals</tt>
//     *    method; <code>false</code> otherwise.
//     * @see #contains(int)
//     */
//    public boolean containsKey(int key) {
//        Entry tab[] = table;
//        int hash = key;
//        int index = (hash & 0x7FFFFFFF) % tab.length;
//        for (Entry e = tab[index]; e != null; e = e.next) {
//            if (e.hash == hash && e.key == key) {
//                return true;
//            }
//        }
//        return false;
//    }
//
//    /***
//     * <p>Returns the value to which the specified key is mapped in this map.</p>
//     *
//     * @param   key   a key in the hashtable.
//     * @return  the value to which the key is mapped in this hashtable;
//     *          0 if the key is not mapped to any value in
//     *          this hashtable.
//     * @see     #put(int, int)
//     */
    public int get(int key) {
        Entry tab[] = table;
        int hash = key;
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry e = tab[index]; e != null; e = e.next) {
            if (e.hash == hash && e.key == key) {
                return e.value;
            }
        }
        return 0;
    }

//    /***
//     * <p>Returns thes value to which the specified key is mapped in this map.</p>
//     *
//     * @param   key   a key in the hashtable.
//     * @return  the values to which the key is mapped in this hashtable;
//     *          <code>null</code> if the key is not mapped to any value in
//     *          this hashtable.
//     * @see     #put(int, int)
//    public ArrayList<Integer> getValues(int key) {
//        Entry tab[] = table;
//        int hash = key;
//        int index = (hash & 0x7FFFFFFF) % tab.length;
//        for (Entry e = tab[index]; e != null; e = e.next) {
//            if (e.hash == hash && e.key == key) {
//                return e.values;
//            }
//        }
//        return null;
//    }
//     */
//    
//    /***
//     * <p>Increases the capacity of and internally reorganizes this
//     * hashtable, in order to accommodate and access its entries more
//     * efficiently.</p>
//     *
//     * <p>This method is called automatically when the number of keys
//     * in the hashtable exceeds this hashtable's capacity and load
//     * factor.</p>
//     */
    protected void rehash() {
        int oldCapacity = table.length;
        Entry oldMap[] = table;

        int newCapacity = oldCapacity * 2 + 1;
        Entry newMap[] = new Entry[newCapacity];

        threshold = (int) (newCapacity * loadFactor);
        table = newMap;

        for (int i = oldCapacity; i-- > 0;) {
            for (Entry old = oldMap[i]; old != null;) {
                Entry e = old;
                old = old.next;

                int index = (e.hash & 0x7FFFFFFF) % newCapacity;
                e.next = newMap[index];
                newMap[index] = e;
            }
        }
    }
//
//    /***
//     * <p>Maps the specified <code>key</code> to the specified
//     * <code>value</code> in this hashtable. The key cannot be
//     * <code>null</code>. </p>
//     *
//     * <p>The value can be retrieved by calling the <code>get</code> method
//     * with a key that is equal to the original key.</p>
//     *
//     * @param key     the hashtable key.
//     * @param value   the value.
//     * @return the previous value of the specified key in this hashtable,
//     *         or <code>null</code> if it did not have one.
//     * @throws  NullPointerException  if the key is <code>null</code>.
//     * @see     #get(int)
//     */
    public int put(int key, int value) {
        // Makes sure the key is not already in the hashtable.
        Entry tab[] = table;
        int hash = key;
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry e = tab[index]; e != null; e = e.next) {
            if (e.hash == hash && e.key == key) {
                int old = e.value;
                //e.addValue(old);
                e.value = value;
                return old;
            }
        }

        if (count >= threshold) {
            // Rehash the table if the threshold is exceeded
            rehash();

            tab = table;
            index = (hash & 0x7FFFFFFF) % tab.length;
        }

         // Creates the new entry.
         Entry e = new Entry(hash, key, value, tab[index]);
         tab[index] = e;
         count++;
         return 0;
    }
//
//    /***
//     * <p>Removes the key (and its corresponding value) from this
//     * hashtable.</p>
//     *
//     * <p>This method does nothing if the key is not present in the
//     * hashtable.</p>
//     *
//     * @param   key   the key that needs to be removed.
//     * @return  the value to which the key had been mapped in this hashtable,
//     *          or <code>null</code> if the key did not have a mapping.
//     */
//    public int remove(int key) {
//        Entry tab[] = table;
//        int hash = key;
//        int index = (hash & 0x7FFFFFFF) % tab.length;
//        for (Entry e = tab[index], prev = null; e != null; prev = e, e = e.next) {
//            if (e.hash == hash && e.key == key) {
//                if (prev != null) {
//                    prev.next = e.next;
//                } else {
//                    tab[index] = e.next;
//                }
//                count--;
//                int oldValue = e.value;
//                e.value = 0;
//                return oldValue;
//            }
//        }
//        return 0;
//    }
//
//    /***
//     * <p>Clears this hashtable so that it contains no keys.</p>
//     */
//    public void clear() {
//    	Entry tab[] = table;
//        for (int index = tab.length; --index >= 0;) {
//            tab[index] = null;
//        }
//        count = 0;
//	}
//
//    /***
//     * <p>Innerclass that acts as a datastructure to create a new entry in the
//     * table.</p>
//     */
    static class Entry {
        int hash;
        int key;
        int value;
        //ArrayList<Integer> values = new ArrayList<Integer>();
        Entry next;

        /***
         * <p>Create a new entry with the given values.</p>
         *
         * @param hash The code used to hash the int with
         * @param key The key used to enter this in the table
         * @param value The value for this key
         * @param next A reference to the next entry in the table
         */
        protected Entry(int hash, int key, int value, Entry next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
            //values.add(value);
        }
/*
        public void addValue(int old) {
        	if (!(hash == 0 || values.contains(old)))
        		values.add(old);
        }
        
        public ArrayList<Integer> getValues() {
        	return values;
        }
*/        
        // extra methods for inner class Entry by Paulo
        public int getKey() {
        	return key;
        }
        public int getValue() {
        	return value;
        }
        @Override
        protected Object clone() {
        	Entry entry = new Entry(hash, key, value, next != null ? (Entry)next.clone() : null);
        	return entry;
        }
    }
//
//    // extra inner class by Paulo
//    static class IntHashtableIterator implements Iterator<Entry> {
//        int index;
//        Entry table[];
//        Entry entry;
//
//        IntHashtableIterator(Entry table[]) {
//        	this.table = table;
//        	this.index = table.length;
//        }
//        public boolean hasNext() {
//        	if (entry != null) {
//        		return true;
//        	}
//        	while (index-- > 0) {
//        	    if ((entry = table[index]) != null) {
//        	        return true;
//        	    }
//        	}
//        	return false;
//        }
//
//        public Entry next() {
//            if (entry == null) {
//                while (index-- > 0 && (entry = table[index]) == null);
//            }
//            if (entry != null) {
//            	Entry e = entry;
//            	entry = e.next;
//            	return e;
//            }
//        	throw new NoSuchElementException(MessageLocalization.getComposedMessage("inthashtableiterator"));
//        }
//        public void remove() {
//        	throw new UnsupportedOperationException(MessageLocalization.getComposedMessage("remove.not.supported"));
//        }
//    }
//
//// extra methods by Paulo Soares:
//
//    public Iterator<Entry> getEntryIterator() {
//        return new IntHashtableIterator(table);
//    }
//
//    public int[] toOrderedKeys() {
//    	int res[] = getKeys();
//    	Arrays.sort(res);
//    	return res;
//    }
//
//    public int[] getKeys() {
//    	int res[] = new int[count];
//    	int ptr = 0;
//    	int index = table.length;
//    	Entry entry = null;
//    	while (true) {
//    		if (entry == null)
//    			while (index-- > 0 && (entry = table[index]) == null);
//    		if (entry == null)
//    			break;
//    		Entry e = entry;
//    		entry = e.next;
//    		res[ptr++] = e.key;
//    	}
//    	return res;
//    }
//
//    public int getOneKey() {
//    	if (count == 0)
//    		return 0;
//    	int index = table.length;
//    	Entry entry = null;
//    	while (index-- > 0 && (entry = table[index]) == null);
//    	if (entry == null)
//    		return 0;
//    	return entry.key;
//    }
//
//    @Override
//    public Object clone() {
//    	try {
//    		IntHashtable t = (IntHashtable)super.clone();
//    		t.table = new Entry[table.length];
//    		for (int i = table.length ; i-- > 0 ; ) {
//    			t.table[i] = table[i] != null
//    			? (Entry)table[i].clone() : null;
//    		}
//    		return t;
//    	} catch (CloneNotSupportedException e) {
//    		// this shouldn't happen, since we are Cloneable
//    		throw new InternalError();
//    	}
//    }
}
